public class Test_8_27 {

    //BM2 链表内指定区间反转
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(head == null || m == n) return head;

        ListNode cur = head;
        ListNode prev = head;
        //1. 走完这个循环，newhead为第m个结点的前驱结点，cur为开始反转结点
        for(int i = m-1; i > 0; i--) {
            prev = cur;
            cur = cur.next;
        }
        //2. 开始反转指定区间的链表，若cur为空且count>n，则要求反转区间异常，返回null
        ListNode newhead = cur;
        ListNode tmp = cur;     //保存反转区间链表的最后一个结点的引用
        cur = cur.next;
        for(int i = n-1;i >= m ; i--) {
            ListNode curNext = cur.next;
            cur.next = newhead;
            newhead = cur;
            cur = curNext;
        }
        //3. 将反转的链表的最后一个结点与后面结点相连
        tmp.next = cur;

        //4. 若从1位置开始反转，则返回newhead；不然则需将反转链表之间的结点与反转链表
        //相连，并返回head结点
        if(m == 1) {
            return newhead;
        }
        prev.next = newhead;
        return head;
    }


    //BM1 反转链表
    public ListNode ReverseList (ListNode head) {
        if(head == null) return null;

        ListNode newhead = new ListNode(head.val);
        head = head.next;
        while(head != null) {
            ListNode next = head.next;
            head.next = newhead;
            newhead = head;
            head = next;;
        }
        return newhead;
    }



    //BM3 链表中的节点每k个一组翻转
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head == null || k == 1) return head;

        ListNode slow = head;
        ListNode fast = head;
        ListNode newHead = new ListNode(-1);
        ListNode tail = newHead;       //记录 最新链表的 尾结点
        while(fast != null) {
            int i = k;
            for(; fast != null && i > 0; i--) {
                fast = fast.next;
            }
            // 此次遍历的链表的长度 < k , 即剩下的链表不用翻转
            if(i > 0) {
                tail.next = slow;
            }
            // 目前有 k 个结点需要反转
            if(i == 0) {
                ListNode flag = slow;       //记录此段链表结点翻转完成后的最后一个结点
                ListNode tmphead = slow;
                slow = slow.next;
                while(slow != fast) {
                    ListNode slowNext = slow.next;
                    slow.next = tmphead;
                    tmphead = slow;
                    slow = slowNext;
                }
                tail.next = tmphead;
                tail = flag;
                //如果整个链表的长度是 k 的整数倍，则 将 tail结点 的next 置为空
                if(fast == null) {
                    tail.next = null;
                }
            }
        }
        return newHead.next;
    }
}
